package leetcode.editor.cn;

import java.util.*;

/**
 * @id: 212
 * @title: 单词搜索 II
 */
 
//给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。 
//
// 单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使
//用。 
//
// 
//
// 示例 1： 
//
// 
//输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l"
//,"v"]], words = ["oath","pea","eat","rain"]
//输出：["eat","oath"]
// 
//
// 示例 2： 
//
// 
//输入：board = [["a","b"],["c","d"]], words = ["abcb"]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// m == board.length 
// n == board[i].length 
// 1 <= m, n <= 12 
// board[i][j] 是一个小写英文字母 
// 1 <= words.length <= 3 * 104 
// 1 <= words[i].length <= 10 
// words[i] 由小写英文字母组成 
// words 中的所有字符串互不相同 
// 
// Related Topics 字典树 数组 字符串 回溯 矩阵 
// 👍 460 👎 0

public class P212WordSearchIi {
    public static void main(String[] args) {
        Solution solution = new P212WordSearchIi().new Solution();
        // todo 
//        char[][] board = {
//                {'o','a','a','n'},
//                {'e','t','a','e'},
//                {'i','h','k','r'},
//                {'i','f','l','v'}
//        };
//        String[] words = {"oath","pea","eat","rain"};
        char[][] board = {
                {'a','a','a','a','a','a','a','a','a','a','a','a'},
                {'a','a','a','a','a','a','a','a','a','a','a','a'},
                {'a','a','a','a','a','a','a','a','a','a','a','a'},
                {'a','a','a','a','a','a','a','a','a','a','a','a'},
                {'a','a','a','a','a','a','a','a','a','a','a','a'},
                {'a','a','a','a','a','a','a','a','a','a','a','a'},
                {'a','a','a','a','a','a','a','a','a','a','a','a'},
                {'a','a','a','a','a','a','a','a','a','a','a','a'},
                {'a','a','a','a','a','a','a','a','a','a','a','a'},
                {'a','a','a','a','a','a','a','a','a','a','a','a'},
                {'a','a','a','a','a','a','a','a','a','a','a','a'},
                {'a','a','a','a','a','a','a','a','a','a','a','a'}
        };
        String[] words = {"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"};
        final List<String> words1 = solution.findWords(board, words);
        System.out.println(words1);
    }
    
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    private class Trie {
        String word = "";
        Map<Character, Trie> nodes = new HashMap<>();
        boolean isWord = false;

        public Trie() {
        }

        public void insert(String word) {
            Trie currNode = this;
            for (int i = 0; i < word.length(); ++i) {
                char c = word.charAt(i);
                if (!currNode.nodes.containsKey(c)) {
                    currNode.nodes.put(c, new Trie());
                }
                currNode = currNode.nodes.get(c);
            }
            currNode.word = word;
            currNode.isWord = true;
        }

        public boolean find(String word) {
            char[] chars = word.toCharArray();
            Trie currNode = this;
            for (char c : chars) {
                final Trie trieNode = currNode.nodes.get(c);
                if (trieNode == null) {
                    return false;
                }
                currNode = trieNode;
            }
            return currNode.isWord;
        }
    }

    private Set<String> ans = new HashSet<>();
    private int wordMaxLen = 0;
    public List<String> findWords(char[][] board, String[] words) {
        int wordCount = words.length;
        int n = board.length;
        int m = board[0].length;
        boolean[][] memo = new boolean[n][m];
        final Trie trie = buildTrie(words);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                findWord(trie, board, memo, i, j, 0);
                if (ans.size() >= wordCount) {
                   break;
                }
            }
            if (ans.size() >= wordCount) {
                break;
            }
        }
        return new ArrayList<>(ans);
    }

    private int[][] direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private void findWord(Trie currTrie,
                            char[][] board,
                            boolean[][] memo,
                            int r,
                            int c,
                            int count) {
        final boolean b = currTrie.nodes.containsKey(board[r][c]);
        if (!b || count > wordMaxLen)
            return;

        final Trie trie = currTrie.nodes.get(board[r][c]);
        if (trie != null && trie.isWord && !"".equals(trie.word))
            ans.add(trie.word);

        memo[r][c] = true;
        ++count;
        for (int[] dire : direction) {
            int newRow = dire[0] + r;
            int newCol = dire[1] + c;
            if (newRow < 0 || newRow >= board.length
                    || newCol < 0 || newCol >= board[0].length
                    || memo[newRow][newCol]) {
                continue;
            }
            findWord(trie, board, memo, newRow, newCol, count);
        }
        memo[r][c] = false;
        --count;
    }

    private Trie buildTrie(String[] words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
            wordMaxLen = Math.max(wordMaxLen, word.length());
        }
        return trie;
    }
}
//leetcode submit region end(Prohibit modification and deletion)


}